package com.cy.linklist;

import sun.applet.Main;

import java.util.HashSet;
import java.util.Stack;

/**
 * @Author: chenyun
 * @Date: 2021/09/22/15:25
 * @Description:
 */

//160. 相交链表
//两个单链表的头节点 headA 和 headB ，
// 请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
public class Demo160 {


    // 思路和Demo141判断链表是否有环同
    // 每次遍历到一个节点时，判断该节点此前是否被访问过
    // 将未访问的点放入HashSet  HashSet已经存在的点再放入时add返回的值为false
    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        HashSet<ListNode> set = new HashSet<>();
        ListNode tem = headA;
        while (tem != null){
            if (set.add(tem)) {
                tem = tem.next;
            }
        }
        tem = headB;
        while (tem != null){

            if (set.add(tem)) {
                // 如果添加的元素set里面无，则加入
                tem = tem.next;
            }else {
                // 如果添加的元素set里面有，则返回
                return headA;
            }
        }
        return null;
    }

    public static void main(String[] args) {
        ListNode A = new ListNode(8);
        ListNode B1 = new ListNode(4);
        ListNode B2 = new ListNode(1);
        ListNode B3 = new ListNode(8);
        ListNode B4 = new ListNode(4);
        ListNode B5 = new ListNode(5);
        B1.next = B2;
        B2.next = B3;
        B3.next = B4;
        B4.next = B5;
        B5.next = null;
        ListNode listNode = getIntersectionNode(A, B1);
        while (listNode != null){
            System.out.println(listNode.val);
            listNode = listNode.next;
        }
    }
}
